package com.example.tree.bst;

import com.example.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class BST {

    public static void main(String[] args) {
        int[] nums = {3, 1 ,7, 4, 6, 2};
        List<Integer> res = new ArrayList<>();
        TreeNode root = null;
        System.out.println("=======================insert===================");
        for (int i = 0; i < nums.length; i++) {
            root = insert(root, nums[i]);
        }

        inorder(root, res);

        res.forEach(e -> {
            System.out.println(e);
        });
        System.out.println(searchBST(root, 2));

        System.out.println("===============delete======================");

        root = delete(root, 3);
        List<Integer> res2 = new ArrayList<>();
        inorder(root, res2);
        res2.forEach(e -> {
            System.out.println(e);
        });
        System.out.println(searchBST(root, 2));

    }

    /**
     * BST插入元素(递归实现)
     * @param root
     * @param value
     */
    public static TreeNode insert(TreeNode root, int value) {
        if (root == null) { // 如果根结点为空，则元素为根结点
            return new TreeNode(value);
        }else if (value < root.val) { // 元素小于根结点值，插入左子树
            root.left = insert(root.left, value);
        }else { // 元素大于等于根结点值，插入右子树
            root.right = insert(root.right, value);
        }
        return root;
    }

    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null)
            return;

        inorder(root.left, res);
        res.add(root.val);
//        System.out.println(root.val);
        inorder(root.right, res);

    }

    /**
     * 检索一棵二叉排序树中是否有target元素
     * @param root
     * @param target
     * @return
     */
    public static boolean searchBST(TreeNode root, int target) {
        if (root == null)
            return false;

        if (root.val == target)
            return true;
        if (target < root.val)
            return searchBST(root.left, target);

        if (target > root.val)
            return searchBST(root.right, target);

        return false;
    }

    /**
     * 删除目标节点(leetcode450)
     *
     * 如果 target > root.val，说明要删除的节点在右子树
     * 如果 target < root.val，说明要删除的节点在左子树
     * 如果 key == root.val，该节点就是我们要删除的节点
     *
     *   1.要删除的节点为叶子节点，可以直接删除
     *
     *   2.要删除的节点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，
     *     该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。
     *
     *   3.要删除的节点不是叶子节点，且没有右节点但是有左节点。
     *     这意味着它的后继节点在它的上面。使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。
     *
     *
     *
     *。
     * @param root
     * @param target
     * @return
     */
    public static TreeNode delete(TreeNode root, int target) {
        if (root == null)
            return null;

        if (target < root.val)
            root.left = delete(root.left, target);

        if (target > root.val)
            root.right = delete(root.right, target);

        if (root.val == target) {
            if (root.left == null && root.right == null) { // 删除的节点是叶子节点
                root = null;
            } else if (root.right != null) {// 删除的节点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代
                // 将当前节点替换成它的直接后继节点
                root.val = successor(root);
                // 从当前节点的右节点递归删除后继节点
                root.right = delete(root.right, root.val);

            } else {// 要删除的节点不是叶子节点，且没有右节点但是有左节点
                // 将当前节点替换成它的直接前驱节点
                root.val = predecessor(root);
                // 从当前节点的左节点递归删除前驱节点
                root.left = delete(root.left, root.val);
            }
        }

        return root;
    }

    /**
     * 找到node的直接后继节点
     *
     * 第一步向左，后面都向右，直到叶子节点为止
     * @param node
     * @return
     */
    private static int successor(TreeNode node) {
        node = node.right;
        while (node.left != null)
            node = node.left;

        return node.val;
    }

    /*

    */

    /**
     * 找到node的直接前驱节点
     *
     * 第一步向左，后面都向右，直到叶子节点为止
     * @param node
     * @return
     */
    private static int predecessor(TreeNode node) {
        node = node.left;
        while (node.right != null)
            node = node.right;

        return node.val;
    }
}
